#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2025/3/19
# @USER    : Shengji He
# @File    : FindPalindromeWithFixedLength.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List

"""
- Array
- Math
"""


class Solution:
    """
    [2217. Find Palindrome With Fixed Length](https://leetcode.com/problems/find-palindrome-with-fixed-length/description/)

    Given an integer array queries and a positive integer intLength, return an array answer where answer[i] is either the queries[i]th smallest positive palindrome of length intLength or -1 if no such palindrome exists.

    A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.

    Example 1:
        Input: queries = [1,2,3,4,5,90], intLength = 3
        Output: [101,111,121,131,141,999]
        Explanation:
        The first few palindromes of length 3 are:
        101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
        The 90th palindrome of length 3 is 999.

    Example 2:
        Input: queries = [2,4,6], intLength = 4
        Output: [1111,1331,1551]
        Explanation:
        The first six palindromes of length 4 are:
        1001, 1111, 1221, 1331, 1441, and 1551.

    Constraints:
        - 1 <= queries.length <= 5 * 104
        - 1 <= queries[i] <= 109
        - 1 <= intLength <= 15
    """

    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        half = (intLength + 1) // 2  # 计算前半部分的位数
        max_count = 9 * (10 ** (half - 1))  # 最大可能的回文数数量
        start = 10 ** (half - 1)  # 前半部分的最小值
        result = []
        for q in queries:
            if q > max_count:
                result.append(-1)
            else:
                first_half = start + (q - 1)  # 计算当前查询对应的前半部分数值
                s = str(first_half)
                # 根据长度奇偶性构造回文数字符串
                if intLength % 2 == 1:
                    palindrome_str = s + s[:-1][::-1]  # 奇数长度，去掉最后一位后反转
                else:
                    palindrome_str = s + s[::-1]  # 偶数长度，直接反转
                result.append(int(palindrome_str))
        return result

    def kthPalindrome_v2(self, queries: List[int], intLength: int) -> List[int]:
        halfLength = (intLength + 1) // 2
        firstHalfBase = 10 ** (halfLength - 1)
        start = intLength % 2

        def get_palindrome(q: int) -> int:
            part1 = str(firstHalfBase + q - 1)

            if len(part1) > halfLength:
                return -1

            return int(part1 + part1[::-1][start:])

        return map(get_palindrome, queries)


if __name__ == '__main__':
    queries = [1, 2, 3, 4, 5, 90]
    intLength = 3

    # queries = [2, 4, 6]
    # intLength = 4

    S = Solution()
    print(S.kthPalindrome(queries, intLength))
    print('done')
